{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum Multiples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumOfMultiples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #倍数求和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>n</code> ，请你计算在 <code>[1，n]</code> 范围内能被 <code>3</code>、<code>5</code>、<code>7</code> 整除的所有整数之和。</p>\n",
    "\n",
    "<p>返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7\n",
    "<strong>输出：</strong>21\n",
    "<strong>解释：</strong>在 <code>[1, 7]</code> 范围内能被 <code>3</code>、<code>5</code>、<code>7</code> 整除的所有整数分别是 <code>3</code>、<code>5</code>、<code>6</code>、<code>7</code> 。数字之和为 <code>21</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10\n",
    "<strong>输出：</strong>40\n",
    "<strong>解释：</strong>在 <code>[1, 10]</code> 范围内能被 <code>3</code>、<code>5</code>、<code>7</code> 整除的所有整数分别是 <code>3</code>、<code>5</code>、<code>6</code>、<code>7</code>、<code>9</code>、<code>10</code> 。数字之和为 <code>40</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 9\n",
    "<strong>输出：</strong>30\n",
    "<strong>解释：</strong>在 <code>[1, 9]</code> 范围内能被 <code>3</code>、<code>5</code>、<code>7</code> 整除的所有整数分别是 <code>3</code>、<code>5</code>、<code>6</code>、<code>7</code>、<code>9</code> 。数字之和为 <code>30</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>1 &lt;= n &lt;= 10<sup>3</sup></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-multiples](https://leetcode.cn/problems/sum-multiples/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-multiples](https://leetcode.cn/problems/sum-multiples/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7', '10', '9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        def sumOfMultiplesHelper(n, divider):\n",
    "            m = n // divider\n",
    "            return divider * m * (1 + m) // 2\n",
    "        result = 0\n",
    "        result += sumOfMultiplesHelper(n, 3)\n",
    "        result += sumOfMultiplesHelper(n, 5)\n",
    "        result += sumOfMultiplesHelper(n, 7)\n",
    "        result -= sumOfMultiplesHelper(n, 15)\n",
    "        result -= sumOfMultiplesHelper(n, 21)\n",
    "        result -= sumOfMultiplesHelper(n, 35)\n",
    "        result += sumOfMultiplesHelper(n, 3 * 5 * 7)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1,n + 1):\n",
    "            if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:\n",
    "                ans += i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1) :\n",
    "            if i % 3 == 0 or i % 5 == 0 or i % 7 == 0 :\n",
    "                ans += i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        def cum(x,y):\n",
    "            return x*(y//x)*(y//x + 1)//2\n",
    "        return cum(3,n) + cum(5,n) + cum(7,n) - cum(15,n) - cum(21,n) - cum(35,n) + cum(105,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        arr = [3, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 24, 25, 27, 28, 30, 33, 35, 36, 39, 40, 42, 45, 48, 49, 50, 51, 54, 55, 56, 57, 60,63, 65, 66, 69, 70, 72, 75, 77, 78, 80, 81, 84, 85, 87, 90, 91, 93, 95, 96, 98, 99, 100, 102, 105, 108, 110, 111, 112, 114, 115, 117, 119, 120, 123, 125, 126, 129, 130, 132, 133, 135, 138, 140, 141, 144, 145, 147, 150, 153, 154, 155, 156, 159, 160, 161, 162, 165, 168, 170, 171, 174, 175, 177, 180, 182, 183, 185, 186, 189, 190, 192, 195, 196, 198, 200, 201, 203, 204, 205, 207, 210, 213, 215, 216, 217, 219, 220, 222, 224, 225, 228, 230, 231, 234, 235, 237, 238, 240, 243, 245, 246, 249, 250, 252, 255, 258, 259, 260, 261, 264, 265, 266, 267, 270, 273, 275, 276, 279, 280, 282, 285, 287, 288, 290, 291, 294, 295, 297, 300, 301, 303, 305, 306, 308, 309, 310, 312, 315, 318, 320, 321, 322, 324, 325, 327, 329, 330, 333, 335, 336, 339, 340, 342, 343, 345, 348, 350, 351, 354, 355, 357, 360, 363, 364, 365, 366, 369, 370, 371, 372, 375, 378, 380, 381, 384, 385, 387, 390, 392, 393, 395, 396, 399, 400, 402, 405, 406, 408, 410, 411, 413, 414, 415, 417, 420, 423, 425, 426, 427, 429, 430, 432, 434, 435, 438, 440, 441, 444, 445, 447, 448, 450, 453, 455, 456, 459, 460, 462, 465, 468, 469, 470, 471, 474, 475, 476, 477, 480, 483, 485, 486, 489, 490, 492, 495, 497, 498, 500, 501, 504, 505, 507, 510, 511, 513, 515, 516, 518, 519, 520, 522, 525, 528, 530, 531, 532, 534, 535, 537, 539, 540, 543, 545, 546, 549, 550, 552, 553, 555, 558, 560, 561, 564, 565, 567, 570, 573, 574, 575, 576, 579, 580, 581, 582, 585, 588, 590, 591, 594, 595, 597, 600, 602, 603, 605, 606, 609, 610, 612, 615, 616, 618, 620, 621, 623, 624, 625, 627, 630, 633, 635, 636, 637, 639, 640, 642, 644, 645, 648, 650, 651, 654, 655, 657, 658, 660, 663, 665, 666, 669, 670, 672, 675, 678, 679, 680, 681, 684, 685, 686, 687, 690, 693, 695, 696, 699, 700, 702, 705, 707, 708, 710, 711, 714, 715, 717, 720, 721, 723, 725, 726, 728, 729, 730, 732, 735, 738, 740, 741, 742, 744, 745, 747, 749, 750, 753, 755, 756, 759, 760, 762, 763, 765, 768, 770, 771, 774, 775, 777, 780, 783, 784, 785, 786, 789, 790, 791, 792, 795, 798, 800, 801, 804, 805, 807, 810, 812, 813, 815, 816, 819, 820, 822, 825, 826, 828, 830, 831, 833, 834, 835, 837, 840, 843, 845, 846, 847, 849, 850, 852, 854, 855, 858, 860, 861, 864, 865, 867, 868, 870, 873, 875, 876, 879, 880, 882, 885, 888, 889, \n",
    "890, 891, 894, 895, 896, 897, 900, 903, 905, 906, 909, 910, 912, 915, 917, 918, 920, 921, 924, 925, 927, 930, 931, 933, 935, 936, 938, 939, 940, 942, 945, 948, 950, 951, 952, 954, 955, 957, 959, 960, 963, 965, 966, 969, 970, 972, 973, 975, 978, 980, 981, 984, 985, 987, 990, 993, 994, 995, 996, 999, 1000]\n",
    "        return sum([i for i in arr if i <= n])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        s = set()\n",
    "        base = i = 3\n",
    "        while i <= n:\n",
    "            s.add(i)\n",
    "            i += base\n",
    "        base = i = 5\n",
    "        while i <= n:\n",
    "            s.add(i)\n",
    "            i += base\n",
    "        base = i = 7\n",
    "        while i <= n:\n",
    "            s.add(i)\n",
    "            i += base\n",
    "        print(s)\n",
    "        return sum(s)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        yu = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i%3==0:\n",
    "                yu += i\n",
    "            elif i%5==0:\n",
    "                yu+=i\n",
    "            elif i%7==0:\n",
    "                yu += i\n",
    "            else:\n",
    "                continue\n",
    "        return yu\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:\n",
    "                ans += i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfMultiples(self, n: int) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            if not i %3 or not i%5 or not i%7:\n",
    "                ans+=i\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
